//二分算法
int LowerBound(int *citations, int citationsSize){
    int left = 0, right = citationsSize - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(citations[citationsSize - mid - 1] >= mid + 1){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return right + 1;
}
int cmp(const void* pa, const void* pb){
    return (*(int*)pa - *(int*)pb);
}
int hIndex(int* citations, int citationsSize) {
    qsort(citations, citationsSize, sizeof(int), cmp);
    int ans = LowerBound(citations, citationsSize);
    return ans;
}

//计数排序
int hIndex(int* citations, int citationsSize) {
    int* hash = (int*)malloc(sizeof(int) * 1001);
    memset(hash, 0, sizeof(int) * 1001);

    for(int i = 0; i < citationsSize; i++){
        hash[citations[i]]++;
    }
    int j = 0, count = 0;
    for(int i = 0; i < 1001; i++){
        while(hash[i]--){
            citations[j++] = i;
        }
    }
    for(int j = citationsSize - 1; j >= 0; j--){
        if(citations[j] <= count){
            break;
        }
        count++;
    }
    free(hash);
    return count;
}

/*给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。*/